{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目描述\n",
    "[P20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/submissions/)\n",
    "\n",
    "Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.\n",
    "\n",
    "An input string is valid if:\n",
    "\n",
    "    Open brackets must be closed by the same type of brackets.\n",
    "    Open brackets must be closed in the correct order.\n",
    "\n",
    "Note that an empty string is also considered valid.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: \"()\"\n",
    "Output: true\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: \"()[]{}\"\n",
    "Output: true\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: \"(]\"\n",
    "Output: false\n",
    "\n",
    "Example 4:\n",
    "\n",
    "Input: \"([)]\"\n",
    "Output: false\n",
    "\n",
    "Example 5:\n",
    "\n",
    "Input: \"{[]}\"\n",
    "Output: true\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解题思路\n",
    "\n",
    ">这种题目思路还是很明确的，就是用stack。\n",
    ">\n",
    ">不过有几点要注意下，我觉着首先对一些比较trivial的case的判断会比较好，主要就是长度为0和为奇数的问题。这样可以“尽快”结束程序，无需进行stack上的操作。然后这里也是用了个简单的映射，因为Python的dict是用的hash，比较便宜。不过这里情况可能不太需要这种映射，不过在其他情况比较复杂的时候这种方法也值得一试。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python代码[98.96%]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:49:39.968228Z",
     "start_time": "2019-01-20T13:49:39.946568Z"
    }
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # length[must be even]\n",
    "        length = len(s)\n",
    "        if length == 0:\n",
    "            return True\n",
    "        if length % 2 == 1:\n",
    "            return False\n",
    "        # match[all]\n",
    "        maps = {\n",
    "            '(':1,\n",
    "            ')':-1,\n",
    "            '[':2,\n",
    "            ']':-2,\n",
    "            '{':3,\n",
    "            '}':-3\n",
    "        }\n",
    "        nums = [maps[i] for i in list(s)]\n",
    "        '''\n",
    "        if sum(nums) != 0:\n",
    "            return False\n",
    "        也可以进行总体上的验证，不过一般没太有必要\n",
    "        '''\n",
    "        # match[all & each][stack]\n",
    "        result = [nums[0]]\n",
    "        for i in range(1, len(s)):\n",
    "            if (result != []) and (nums[i] + result[-1]) == 0:\n",
    "                result.pop()\n",
    "            else:\n",
    "                result.append(nums[i])\n",
    "        if result != []:\n",
    "            return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T13:50:17.613081Z",
     "start_time": "2019-01-20T13:50:17.588337Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = Solution()\n",
    "s.isValid(\"{[]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
